package com.fengye.algorithms.leecode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author fengye
 * @Date 2023/4/8 10:37
 **/
public class Permute46 {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if(nums.length == 0) {
            return result;
        }
        if(nums.length == 1) {
            List<Integer> temp = new ArrayList<>();
            temp.add(nums[0]);
            result.add(temp);
            return result;
        }

        doOrder(result, nums, nums.length);
        return result;
    }

    public void doOrder(List<List<Integer>> result, int[] nums, int size) {
        if(size <= 1){
            return;
        }

        for (int i = 0; i < size;i++) {
            doOrder(result, nums, size-1);
            if(size == 2) {
                List<Integer> temp = new ArrayList<>();
                for (int j = 0; j < nums.length;j++) {
                    temp.add(nums[j]);
                }
                result.add(temp);
            }
            rotate(nums, size);
        }

    }

    public void rotate(int[] nums, int size) {
        int pos = nums.length - size;
        int temp = nums[pos];
        int i=0;
        for(i=pos+1;i<nums.length;i++) {
            nums[i-1] = nums[i];
        }
        nums[i-1] = temp;
    }
}
